The present invention relates to a method and apparatus for lock caching, and more specifically, to a method and apparatus for using distributed resource objects to manage locks to control access to resources.
Computers use resources, such as memory, modems and printers, during the execution of computer programs. Many of these resources are only used periodically by any given computer program. For example, the amount of time a word processing application requires a printer to print documents is typically small relative to the amount of time that the word processing application is used to create documents. If the only process that had access to the printer was a single word processing application, the printer would remain idle most of the time.
To take full advantage of resources, computer networks have been developed in which processes running on many computer devices or xe2x80x9cnodesxe2x80x9d can share resources. Thus, instead of having to purchase one printer for every computer, users may purchase a single printer that may be connected to a network that has many computers. Processes on each computer on the network access the printer only when the processes require the printer.
Even though resources may be shared, as described above, many resources may not be used by more than one process at any given time. For example, most printers are unable to print more than one document at a time. Other resources, such as data blocks of a storage medium or tables stores on a storage medium, may be concurrently accessed in some ways (e.g. read) by multiple processes, but accessed in other ways (e.g. written to) by only one process at a time. Consequently, mechanisms have been developed which control access to resources.
One such mechanism is referred to as a lock. A lock is a data structure that indicates that a particular process has been granted certain rights with respect to the resource. There are many types of locks. Some types of locks may be shared by many processes, while other types of locks prevent any other locks to be granted on the same resource. FIG. 1a illustrates a hierarchy of lock modes that may be used to govern access to a table in a database.
At the lowest level in the hierarchy is a NULL mode lock 160. Ownership of a NULL mode lock on a table grants a process no permission to access the table in any manner. Ownership of a concurrent read lock 158 grants a process permission to read the table, but does not guarantee that other processes are not concurrently writing to the table. Ownership of a protected read lock 154 grants a process permission to read the table and guarantees that no other process is concurrently writing to the table. Ownership of a concurrent write lock 156 grants a process permission to write to the table, but does no guarantee that another process is not also writing to the table. Ownership of a protected write lock 152 grants a process permission to write to the table and guarantees that another process is not also writing to the table. Ownership of an exclusive mode lock 150 grants a process permission to do anything with a table, and guarantees that no other process is performing any operation on the table.
Due to the various permissions and guarantees associated with these locks, certain lock combinations are not allowed. For example, if a process owns an exclusive mode lock on a resource, then no other process can be granted any lock other than a NULL mode lock. If a process owns a protected write lock, then no other process may be granted an exclusive mode lock, a protected write lock, a protected read lock or a concurrent write lock. If a process owns a protected read lock, then no other process may be granted an exclusive mode lock, a protected write lock or a concurrent write lock. If a process owns a concurrent write lock, then no other process may be granted an exclusive mode lock, a protected write lock, or a protected read lock. If a process owns a concurrent read lock, then no other process may be granted an exclusive mode lock.
A category of lock that may be held by more than one process at a time is referred to as a shared lock. For example, two processes can hold concurrent read locks on the same resource at the same time, so concurrent read locks are shared locks. For the purposes of explanation, the following description shall refer to exclusive mode locks, shared mode locks, and NULL mode locks.
Before a process can perform an operation on a resource, the process is required to obtain a lock that grants to the process the right to perform the desired operation on the resource. To obtain a lock, a process transmits a request for the lock to a lock manager. A lock manager is a process that is responsible for granting, queuing, and keeping track of locks on one or more resources. To manage the use of resources in a network system, lock managers are executed on one or more nodes in the network.
According to one prior art implementation, a lock management implements two types of objects: a resource object and a lock. Resource objects are data structures that correspond to actual resources. An application that uses a lock manager establishes a mapping between actual resources and resource objects. Each resource object has two queues: a granted queue and a convert queue. The granted queue is an unordered list of locks that have been granted. The convert queue is a partially ordered list of locks that have been requested, but not yet granted. Typically, a request for a lock is actually a convert request, where a process holding a lock is requesting that the lock is holds be converted from one mode of lock to a different mode of lock.
Locks are data structures that identify a process and a lock mode. Lock managers attach locks to the grant queues of resource objects to indicate that the process identified in the lock has been granted a lock of the type indicated in the lock on the resource that corresponds to the resource object to which the lock is attached.
FIG. 1b is a block diagram illustrating a typical lock manager 106. Lock manager 106 is a process that is configured to manage a resource object 100 stored in a memory 108. The resource object 100 includes a granted queue 102 and a convert queue 104. Lock manager 106 has attached three locks 110, 112 and 114 to the granted queue 102, and one convert request 130 to the convert queue 104.
All locks and convert requests have a process ID portion and a lock mode portion. The process ID portion 116 of lock 110 indicates that a process PROC_1 owns lock 110, and the lock mode portion 118 of lock 110 indicates that lock 110 is an exclusive lock. The process ID portion 120 of lock 112 indicates that lock 112 is owned by a process PROC_2, and the lock mode portion 122 of lock 112 indicates that lock 112 is a NULL mode lock. The process ID portion 124 of lock 114 indicates that lock 114 is owned by a process PROC_3, and the lock mode portion 126 of lock 114 indicates that lock 114 is a NULL lock. The process ID portion 132 of convert request 130 indicates that convert request 130 is associated with process PROC_4, and the lock mode portion 136 of convert request 130 indicates that PROC_4 currently holds a NULL mode lock on the resource. In addition to a lock mode portion 136, convert request 130 has a requested mode portion 134 that indicates that PROC_4 is requesting an exclusive mode lock.
Lock manger 106 has attached locks 110, 112 and 114 to granted queue 102, indicating that PROC_1 currently has exclusive ownership of the resource that corresponds to resource object 100. Lock manager 106 has attached convert request 130 to the convert queue 104, indicating that PROC_4 has requested but has not yet been granted an exclusive mode lock on the resource associated with resource object 100.
Information pertaining to any given resource may be stored in the resource object that corresponding to the resource. Each resource object is stored in the memory of a single node. The node on which a resource object is stored is referred to as the master node for the resource object.
According to one lock management approach, a process initially establishes a NULL mode lock on all resources that the process will possibly use. Then, when the process actually requires access to a resource, the process requests that its NULL mode lock be converted to a lock that grants to the process the rights to perform the desired operation.
For example, to delete a table, a process must obtain an exclusive mode lock on the resource object that corresponds to the table. To obtain the exclusive mode lock, the process transmits a message to the lock manager that controls the resource object that corresponds to the table. In the message, the process requests that its current NULL mode lock be converted to an exclusive mode lock. If no other process has requested a conversion, and if no currently granted locks would prevent the grant of an exclusive mode lock, than the current lock held by the requesting process is converted to an exclusive mode lock. Once the lock manager performs the requested conversion, the lock manager transmits a message to the requesting process to indicate that the requested conversion operation has been performed.
If a process requires access to read data from a table, the process must obtain a shared mode lock. To obtain a shared mode lock, the process requests the lock manager that controls the resource object that corresponds to the table to convert its current lock to a shared mode lock. If no other process has requested a conversion, and if no currently granted locks would prevent the grant of a shared mode lock, then the current lock held by the requesting process is converted to a shared mode lock.
If an exclusive mode lock has already been granted for the table, then a shared mode lock cannot be granted. Under these circumstances, the lock convert request is placed on the convert queue of the resource object. When the blocking process is ready to release its exclusive lock, the blocking process may send a lock downgrade request to the lock manager. The lock manager responds by converting the exclusive mode lock to a lesser lock that allows the grant of the shared mode lock. The shared mode lock is then granted by moving the shared mode lock request from the requested queue to the granted queue and transmitting a message to the requesting process to inform the requesting process that the shared mode lock has been granted.
The convert queue of a resource object is a partially ordered list that holds all outstanding (ungranted) lock requests. If any outstanding lock requests have not been granted, one of the ungranted lock requests will be at the xe2x80x9cheadxe2x80x9d of the convert queue. Even if the currently granted locks do not prevent a lock manager from granting a particular lock request, the lock request is placed on the convert queue if the converter queue is not empty. This policy prevents xe2x80x9clivelocksxe2x80x9d, where one process cannot make progress in the system while other processes can.
In networked computer systems, some or all of the processes that are holding and requesting locks on a particular resource may be on different nodes than the node that contains the resource object that corresponds to the resource. For example, the process desiring a lock and the lock resource may reside within different nodes of a multi-processor machine, or on different workstations in a local area network. Consequently, all of the messages that pass between the lock-requesting processes and the lock manager must be transmitted between nodes over the network. The computational power that must be expended to facilitate such inter-node messages is significant relative to the power required for intra-node communication. In addition, inter-node communication is generally slower than inter-node communication. Further, the inter-node traffic thus generated reduces the throughput available for other types of inter-node traffic, which may be significant when the inter-node traffic is between workstations on a network.
FIG. 2 illustrates a computer system in which four nodes 202, 206, 210 and 214 are connected through a network 216. Nodes 202, 206 and 210 are executing process 204 (PROC_1), process 208 (PROC_2) and process 212 (PROC_3), respectively. Lock manager 106 resides on node 214. Every time one of processes 204, 208 and 212 wish to acquire, upgrade, downgrade or release a lock on a resource object controlled by lock manager 106, the processes must send messages to node 214 through network 216. Even time a convert request is granted on lock manager 106, a message must be sent from node 214 to the node on which resides the process that requested the lock conversion.
Based on the foregoing, it is clearly desirable to provide a mechanism for allocating locks between processes that requires less inter-node traffic. It is further desirable to increase the ratio of intra-node communication relative to inter-node communication to provide mode efficient communication between processes.
A generalized method and system for lock caching is provided. The one resource object per resource architecture of the prior art is replaced with a distributed resource object architecture to spread the lock management processing load for any given resource among multiple nodes and the reduce the amount of inter-node traffic required to perform lock management operations. The amount of inter-node traffic is reduced such that the amount of lock a management related inter-node traffic generated in the worst case conditions for the present invention will not exceed the amount of lock management related inter-node traffic generated in a lock management system that uses a single, centralized resource object to manage locks for each resource.
In the distributed resource object lock management system described herein, shadows of a resource object for any given resource may be spread over many nodes, effectively turning the resource object into a distributed object. Consequently, the processing power of multi-processing systems may be exploited in that each of the nodes that has a shadow resource object may be used to perform lock operations related to the resource. Further, because the lock management workload for a resource is distributed, the processing load required to perform lock management for the resource is less likely to overburden a node than in lock management systems in which all lock operations for a resource must be performed at a single node.
According to one aspect of the invention, the master resource object for a resource grants locks to shadow resource objects located on the nodes on which are located the processes that desire to access the resource. Each shadow resource object grants locks on the resource to the processes that are located on the same node as the shadow resource object. The master resource object may also acts as a shadow resource object to the processes running on the master node that require access to the resource owned by the master resource object.
The locked owned by each shadow resource object determines the types of locks the shadow resource object is allowed to grant to processes. If the lock owned by a shadow resource object does not give the shadow resource object the right to grant a lock requested by a process on the same node as the shadow resource object, then the shadow resource object may request for a lock upgrade from the master resource object.
Because the processes that use a resource do not have to cummunicate directly with the master resource object, the amount of inter-node traffic required by the distributed lock management system may be less than that required by lock management systems that employ a single centralized resource object for each resource. Specifically, inter-node traffic is avoided when the shadow resource object owns a lock that allows the shadow resource object to perform a requested lock operation without communicating with the master resource object.
According to one aspect of the invention, a method for managing use of a resource in a computer system is provided. According to the method, a master resource object executes on a first node in the computer system. The master resource object grants locks on the resource in response to lock requests from entities in the computer system when the lock requests are compatible with locks already granted by the master resource object.
Lock information is stored in a second node. The lock information includes information about any locks held on the resource by processes located in the second node. When a process located in the second node requests a particular type of lock on the resource, it is determined whether the requested lock may be granted based on the lock information stored in the second node. The lock is granted to the process without transmitting a lock request to the master resource object of the first node if the requested lock may be granted based on the lock information stored in the second node.
According to one embodiment, the lock information in the second node includes at least one shadow lock that may be owned by a plurality of processes. The second node includes a separate shadow lock for each type of lock that the local lock manager on the second node has requested from the master resource object. When shadow locks are used, the step of determining whether the requested lock may be granted based on the lock information stored in the second node includes determining whether a shadow lock for the particular type of lock is stored in the second node.
If a shadow lock for the requested mode exists on the second node, the step of granting the lock to the process includes updating the shadow lock for the requested mode to indicate that the shadow lock is owned by the process. If a shadow lock for the requested mode does not exist on the second node and the process requesting the lock is the sole owner of a shadow lock for another mode, then the step of granting the lock to the process includes upgrading to the shadow lock that the process currently holds. If a shadow lock for the requested mode does not exist on the second node and the process requesting the lock is not the sole owner of a shadow lock for another mode, then the step of granting the lock to the process includes creating a shadow lock for the requested mode and updating the newly created shadow lock to indicate that the shadow lock is owned by the process.
According to one embodiment, a shadow resource object executes on the second node. The lock information in the second node includes data that indicates a type of lock on the resource owned by the shadow resource object and granted by the master resource object. The shadow resource object grants locks to the processes located on the second node based on the lock owned by the shadow resource object and the locks that have already been granted by the shadow resource object. If a process on the second node requests a lock that is more restrictive than the lock owned by the shadow resource object, then the shadow resource object requests a lock upgrade from the master resource object.